package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *SpiralMatrix_54 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
 *describe: 找规律 AC 100%
 *2018年5月6日 下午4:57:44
 */
public class SpiralMatrix_54 {
	List<Integer> res;
	public static void main(String[] args) {
		SpiralMatrix_54 test=new SpiralMatrix_54();
		//int nums[][]=new int [][] {{1,2,3},{4,5,6},{7,8,9}};
		//int nums[][]=new int [][] {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
		int nums[][]=new int[][] {{1,11},{2,12},{3,13},{4,14},{5,15},{6,16},{7,17},{8,18},{9,19},{10,20}};
		test.spiralOrder(nums);

	}
	
	public List<Integer> spiralOrder(int[][] matrix) {
		int count=0;//圈数
		int row=matrix.length;//行
		if(row==0)
			return new ArrayList<Integer>();
		int col=matrix[0].length;//列
		int total=col*row;
		this.res=new ArrayList<Integer>();
		int index=row>col?col:row;
		while(count<(index%2==0?index/2:index/2+1)) {
			for(int i=0+count;i<col-count;++i) {//遍历完列
				this.res.add(matrix[count][i]);
			}
			for(int i=count+1;i<row-count;++i)
				this.res.add(matrix[i][col-count-1]);
			if(this.res.size()==total)
				return this.res;
			for(int i=col-count-2;i>=0+count;--i)
				this.res.add(matrix[row-count-1][i]);
			for(int i=row-count-2;i>=0+count+1;--i)
				this.res.add(matrix[i][count]);
			++count;
		}
        return this.res;
    }

}
